﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol279{

public int NumSquares2(int targrt)
    {
        //先找一下最小的数，min2=target
        int maxNum=(int)Math.Sqrt(targrt);
        Console.WriteLine("maxNum"+maxNum);
        int[] dp = new int[targrt+1];
        for(int i = 1; i <= targrt; i++)
        {
            dp[i] = targrt;
        }
        dp[0] = 0;

        for (int i = 1; i <= targrt; i++)
        {
            int min = targrt + 2;//这里设置最大值
            for (int j = 1; j <= maxNum; j++)//我的写法
            {
                if (i >=j * j)
                {
                   

                    min =Math.Min(min, dp[i - j * j]);   
                }

                

            }
            dp[i] = min + 1;
            
        }
        


        return dp[targrt];
    }
    
        public int NumSquares(int n)
        {
            int[] f = new int[n + 1];
            for (int i = 1; i <= n; i++)
            {
                int minn = int.MaxValue;
                for (int j = 1; j * j <= i; j++)//非常巧妙的写法，j的平方不是小于target，而是小于当前的i
                {
                    minn = Math.Min(minn, f[i - j * j]);
                }
                f[i] = minn + 1;
            }
            return f[n];
        }
   




    }
class Program279
{

    static void Main279(string[] args)
    {

Sol279 s = new Sol279();
        int target = 13;
       int res= s.NumSquares(target);
        Console.WriteLine(res);
    }
}